#include "pch.h"
#include "GraphMtx.h"

void InitGraph(GraphMtx *g) {
	g->MaxVertices = DEFAULT_VERTICES_SIZE;
	g->NumVertices = g->NumEdges = 0;
	g->VerticesList = (T*)calloc(g->MaxVertices, sizeof(T));
	assert(g->VerticesList != NULL);

	g->Edge = (int**)calloc(g->MaxVertices, sizeof(int*));
	assert(g->Edge != NULL);
	for (size_t i = 0; i < g->MaxVertices; i++) {
		g->Edge[i] = (int*)calloc(g->MaxVertices, sizeof(int));
		memset(g->Edge[i], MAX_COST, sizeof(g->Edge[i]));
	}
		
}

int GetVertexPos(GraphMtx *g, T v) {
	for (size_t i = 0; i < g->NumVertices; i++) {
		if (g->VerticesList[i] == v)
			return i;
	}
	return -1;
}

void ShowGraph(GraphMtx *g) {
	printf("  ");
	for (size_t i = 0; i < g->NumVertices; i++)
	{
		printf("%c ", g->VerticesList[i]);
	}
	printf("\n");
	for (size_t i = 0; i < g->NumVertices; i++) {
		printf("%c ", g->VerticesList[i]);
		for (size_t j = 0; j < g->NumVertices; j++) {
			if (g->Edge[i][j] == MAX_COST){
				cout << "@ ";
			}
			else {
				printf("%d ", g->Edge[i][j]);
			}			
		}
		printf("\n");
	}
	printf("\n");
}

void InsertVertex(GraphMtx *g, T v) {
	if (g->NumVertices >= g->MaxVertices)
		return;
	g->VerticesList[g->NumVertices++] = v;
}

void InsertEdge(GraphMtx *g, T v1, T v2,E cost) {
	int p1 = GetVertexPos(g, v1), p2 = GetVertexPos(g, v2);
	if (p1 == -1 || p2 == -1)
		return;
	
	g->Edge[p1][p2] = cost;
	g->NumEdges++;
}

void RemoveEdge(GraphMtx *g, T v1, T v2) {
	int p1 = GetVertexPos(g, v1), p2 = GetVertexPos(g, v2);
	if (p1 == -1 || p2 == -1)
		return;
	if (g->Edge[p1][p2] ==0)
		return;
	g->Edge[p1][p2] = g->Edge[p2][p1] = 0;
	g->NumEdges--;
}

void RemoveVertex(GraphMtx *g, T v) {
	int p = GetVertexPos(g, v);
	if (p == -1)return;
	int numedges = 0;
	for (size_t i = p; i < g->NumVertices - 1; i++, g->VerticesList[i] = g->VerticesList[i + 1]);
	for (size_t i = 0; i < g->NumVertices; i++, numedges += (g->Edge[p][i] != 0 ? 1 : 0));
	for (size_t i = p; i < g->NumVertices - 1; i++, g->Edge[i] = g->Edge[i + 1]);
	for (size_t i = p, j = 0; i < g->NumVertices - 1, j < g->NumVertices; i++, j++, g->Edge[j][i] = g->Edge[j][i + 1]);
	g->NumEdges-=numedges;
	g->NumVertices--;
}

void DestroyGraph(GraphMtx *g) {
	free(g->VerticesList);
	g->VerticesList = NULL;
	for (size_t i = 0; i < g->MaxVertices; i++) {
		free(g->Edge[i]);
	}
	free(g->Edge);
	g->Edge = NULL;
	g->MaxVertices = g->NumEdges = g->NumVertices = 0;
}

int GetFirstNeighbor(GraphMtx *g, T v) {
	size_t p = GetVertexPos(g, v);
	if (p == -1)return -1;
	for (size_t i = 0; i < g->NumVertices; i++)
	{
		if (g->Edge[p][i] == 1)
			return i;
	}
	return -1;
}

int GetNextNeighbor(GraphMtx *g, T v, T w) {
	int pv = GetVertexPos(g, v), pw = GetVertexPos(g, w);
	if (pv == -1 || pw == -1)return -1;
	for (size_t i = pw + 1; i < g->NumVertices; i++) {
		if (g->Edge[pv][pw] == 1)
			return i;
	}
	return -1;
}

int cmp(const void *a, const void *b)
{
	return ((*(Edge*)a).cost - (*(Edge*)b).cost);
}
bool Is_same(int *father, int x, int y)
{
	for (; father[x] != y; x = father[x]);
	for (; father[y] != y; y = father[y]);
	return x == y;
}
void make_same(int *father, int x, int y)
{
	for (; father[x] != x; x = father[x]);
	for (; father[y] != y; y = father[y]);
	father[y] = x;
}
void MinSpanTree_Kruskal(GraphMtx *g) {
	int n = g->NumVertices;
	Edge *edge = (Edge*)malloc(sizeof(Edge)*(n*(n - 1) / 2));
	assert(edge != NULL);

	int k = 0;
	for (size_t i = 0; i < n; i++)
	{
		for (size_t j = i; j < n; j++)
		{
			if (g->Edge[i][j] != 0 && g->Edge[i][j] != MAX_COST) {
				edge[k].x = i;
				edge[k].y = j;
				edge[k].cost = g->Edge[i][j];
			}
		}
	}

	int v1, v2;
	for (size_t i = 0; i, k; i++)
	{
		v1 = edge[i].x;
		v2 = edge[i].y;
		cout << g->VerticesList[v1] << "->" << g->VerticesList[v2] << ":" << edge[i].cost << endl;
	}
	qsort(edge, k, sizeof(Edge), cmp);

	int *father = (int*)malloc(sizeof(int)*n);
	assert(father != NULL);
	for (size_t i = 0; i < n; i++)
	{
		father[i] = i;
	}
	for (size_t i = 0; i < n; i++)
	{
		if (!Is_same(father, edge[i].x, edge[i].y)) {
			v1=edge[i].x;
			v2=edge[i].y;
			cout<< g->VerticesList[v1]<< "->"<<g->VerticesList[v1]<<":"<< edge[i].cost<<endl;
			make_same(father, edge[i].x, edge[i].y);
		}
	}
}